//
// Created by 1 on 2020-10-13.
//

#include "Solution.h"
#include <vector>
using namespace std;

#ifndef CTY_BINARYSEARCHNORMAL_H
#define CTY_BINARYSEARCHNORMAL_H


class BinarySearchNormal:Solution<int> {
public:
//    int anw(int n, int v, vector<int>& a){
//        int middle = n / 2;
//        if(middle >= a.size() || middle < 0)
//            return a.size() + 1;
//        if(a.at(middle)> v){
//            anw( middle - 1, v, a);
//        }else if(a.at(middle) < v){
//            anw( (middle + 1) *2, v, a);
//        }else if(a.at(middle) == v){
//            return middle;
//        }else{
//            return a.size() + 1;
//        }
//    }

//    int anw(int n, int v, vector<int>& a){
//        int * p1 = &a[n - 1];
//        int * p2 = &a[0];
//        int start = 0;
//        int end = n - 1;
//        while(p1 != p2){
//            p1 --;
//            end --;
//            p2 ++;
//            start ++;
//            if(*p1 == v){
//                return end;
//            }
//            if(*p2 == v){
//                return start;
//            }
//        }
//        return a.size() + 1;
//    }

    int anw(int n, int v, vector<int>& a) {
        int start = 0;
        int end = n;
        while(start < end){
            int middle = (start + end) / 2;
            if(a[middle] < v){
                start = middle + 1;
            }else{
                end = middle;
            }
        }
        return start + 1;
    }

    void selfTest(){
        vector<int> tt;
        tt.push_back(1);
        tt.push_back(2);
        tt.push_back(4);
        tt.push_back(4);
        tt.push_back(5);
        int index = anw(5, 4, tt);
        cout << index << endl;
    }
};


#endif //CTY_BINARYSEARCHNORMAL_H
